#include "list.h"

/**
 * @brief 找到环形链表的入口结点
 *
 * @param head
 * @return ListNode*
 */
ListNode* detectCycle(ListNode* head) {
  if (head == nullptr) {
    return nullptr;
  }
  ListNode *fast = head, *slow = head;

  while (fast && fast->next_) {
    fast = fast->next_->next_;
    slow = slow->next_;

    if (slow == fast) {
      break;
    }
  }

  if (!fast || !fast->next_) {
    return nullptr;
  }

  slow = head;
  while (slow != fast) {
    slow = slow->next_;
    fast = fast->next_;
  }

  return fast;
}